package org.example.Soution001;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class PIBuildTree {
    public static void main(String[] args) {
        int[] preorder = { 3,9,20,15,7 };
        int[] inorder = {9,3,15,20,7};
        PIBuildTree tree = new PIBuildTree();
        TreeNode treeNode=tree.buildTree(preorder, inorder);
        System.out.println(treeNode.val+" "+treeNode.left.val+" "+treeNode.right.right.val);

    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //判断是不是只有一个元素
        if(preorder.length == 1) return new TreeNode(preorder[0]);
        //用栈，以中序为比较标准，把先序一个个推进去，找到最大的出栈元素
        Stack<TreeNode> st = new Stack<TreeNode>();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int count=0;
        for(int num:inorder){
            map.put(num, count);
            count++;
        }
        TreeNode root = new TreeNode(preorder[0]);
        st.push(root);
        for(int i=1;i<preorder.length;i++){
            TreeNode temp = null;
            TreeNode newNode = new TreeNode(preorder[i]);
            while(!st.isEmpty()&&map.get(st.peek().val)<map.get(preorder[i])){
                temp=st.pop();
            }
            if(st.isEmpty()||(temp!=null&&temp.right==null)){
                temp.right=newNode;
            }else{
                st.peek().left = newNode;
            }
            st.push(newNode);
        }
        return root;
    }
}
